package problem126_Word_Ladder_II;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class Mysolution {
	private Set<String> wordList;
	private List<List<String>> result;
	
	public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        this.wordList=wordList;
        result=new LinkedList<>();
        dfs(beginWord,endWord,new LinkedList<>());
        return result;
    }
	
	private void dfs(String begin,String end,List<String> current){
		current.add(begin);
		if(result.size()!=0){
			if(current.size()>=result.get(result.size()-1).size()){
				return;
			}
		}
		if(successfulTrans(begin,end)){
			current.add(end);
			if(result.size()!=0){
				if(current.size()<result.get(result.size()-1).size()){
					result.clear();
				}	
			}
			result.add(new LinkedList<>(current));
			current.remove(current.size()-1);
			return;
		}
		List<String> possibleNext=possibleNext(begin,wordList);
		for(String next:possibleNext){
			if(!current.contains(next)){
				dfs(next,end,current);
				current.remove(current.size()-1);
			}
		}
	}
	
	private List<String> possibleNext(String begin,Set<String> wordList){
		List<String> result=new LinkedList<>();
		for(String end:wordList){
			if(successfulTrans(begin,end))
				result.add(end);
		}
		return result;
	}
	
	private boolean successfulTrans(String begin,String end){
		int diff=0;char[] beg=begin.toCharArray();
		char[] ends=end.toCharArray();
		for(int i=0;i<beg.length;i++){
			if(beg[i]!=ends[i]){
				diff+=1;
				if(diff>1)
					return false;
			}	
		}
		return diff==1;
	}
	
	public static void main(String[] args){
		Set<String> words=new HashSet<>(Arrays.asList(new String[]{"hot","dot","dog","lot","log"}));
		System.out.println(new Mysolution().findLadders("hit", "cog", words));
	}
}
